package org.example;

import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

// 二叉树
/*
 * 几种常见的二叉树
 * 1. 满二叉树
 * 满二叉树有个优势，就是它的节点个数很好算。假设深度为h，那么总节点数就是2^h-1,
 * 2. 完全二叉树
 * 完全二叉树是指，二叉树的每一层的节点都紧凑靠左排列，且除了最后一层，其他每层都必须是满的，所以满二叉树其实是一种特殊的完全二叉树。
 * 完全二叉树的特点：由于它的节点紧凑排列，如果从左到右从上到下对它的每个节点编号，那么父子节点的索引存在明显的规律。
 * 完全二叉树数的左右子树也是完全二叉树，换句话说：完全二叉树的左右子树中，至少有一棵是满二叉树。
 * 3. 二叉搜索树
 * 二叉搜索树（Binary Search Tree，简称 BST）是一种很常见的二叉树，它的定义是：对于树中的每个节点，
 * 其左子树的每个节点的值都要小于这个节点的值，右子树的每个节点的值都要大于这个节点的值。你可以简单记为「左小右大」。
 * BST是非常实用的数据结构，因为左小右大的特征，可以让我们在BST中快速找到某个节点，或者找到某个范围内的所有节点，这个BST的优势所在。
 * 4. 平衡二叉树
 * 平衡二叉树（Balanced Binary Tree）是一种特殊的二叉树，它的每个节点的左右子树的高度差不超过1.
 *
 * 二叉树的递归/层序遍历
 * 二叉树只有递归遍历和层序遍历这两种，再无其他。递归遍历可以衍生出 DFS 算法，层序遍历可以衍生出 BFS 算法。
 * 递归遍历二叉树节点的顺序是固定的，但是有三个关键位置，在不同位置插入代码，会产生不同的效果。
 * 层序遍历二叉树节点的顺序也是固定的，但是有三种不同的写法，对应不同的场景。
 * */
public class BinaryTree {
    static class TreeNode {
        int val;
        TreeNode left, right;
    }

    // // 递归遍历（DFS）：二叉树的递归遍历框架
    void traverse(TreeNode root) {
        if (root == null) {
            return;
        }
        // 前序位置
        traverse(root.left);
        // 中序位置
        traverse(root.right);
        // 后序位置
    }

    // 前序遍历、中序遍历、后序遍历

    /**
     * 注意三个递归方式中的时机
     * 1. 前序位置的代码会在进入节点时立即执行；
     * 2. 中序位置的代码会在左子树遍历完成后，遍历右子树之前执行；
     * 3. 后序位置的代码会在左右子树遍历完成后执行：
     */

    // 层序遍历（BFS）：一层一层地遍历二叉树，层序遍历需要借助队列来实现，而且根据不同的需求，可以有三种不同的写法
    static class LevelOrderTraverse {
        // 写法一：
        // 这种写法的优缺点：最大的优势就是简单。每次把队头元素拿出来，然后把它的左右子节点加入队列，就完事了。
        // 但是这种写法的缺点是，无法知道当前节点在第几层。知道节点的层数是个常见的需求，比方说让你手机每一层的节点，或者计算二叉树的最小深度等等。
        void levelOrderTraverse1(TreeNode root) {
            if (root == null) {
                return;
            }
            Queue<TreeNode> queue = new LinkedList<>();
            queue.offer(root);
            while (!queue.isEmpty()) {
                TreeNode cur = queue.poll();
                // 访问cur节点
                System.out.println(cur.val);

                // 把cur的左右子节点加入队列
                if (cur.left != null) {
                    queue.offer(cur.left);
                }
                if (cur.right != null) {
                    queue.offer(cur.right);
                }
            }
        }

        // 写法二：
        void levelOrderTraverse2(TreeNode root) {
            if (root == null) {
                return;
            }
            Queue<TreeNode> queue = new LinkedList<>();
            queue.offer(root);
            // 记录当前遍历到的层数（根节点视为第1层）
            int depth = 1;
            while (!queue.isEmpty()) {
                // 但是注意队列的长度 sz 一定要在循环开始前保存下来，因为在循环过程中队列的长度是会变化的，
                // 不能直接用 queue.size() 作为循环条件。
                int sz = queue.size();
                for (int i = 0; i < sz; i++) {
                    TreeNode cur = queue.poll();
                    // 访问cur节点，同时知道它所在的层数
                    System.out.println("depth = " + depth + ", val = " + cur.val);

                    // 把cur的左右子节点加入队列
                    if (cur.left != null) {
                        queue.offer(cur.left);
                    }
                    if (cur.right != null) {
                        queue.offer(cur.right);
                    }
                }
                depth++;
            }
        }

        // 写法三：
        // 回顾写法二，我们每向下遍历一层，就给 depth 加 1，可以理解为每条树枝的权重是 1，
        // 二叉树中每个节点的深度，其实就是从根节点到这个节点的路径权重和，且同一层的所有节点，路径权重和都是相同的。
        // 写法三就是为了解决这个问题，在写法一的基础上添加一个 State 类，让每个节点自己负责维护自己的路径权重和

        // 这样每个节点都有了自己的depth变量，是最灵活的，可以满足所有的BFS算法的需求
        void levelOrderTraverse3(TreeNode root) {
            if (root == null) {
                return;
            }
            Queue<State> queue = new LinkedList<>();
            // 根节点的路径权重和是1
            queue.add(new State(root, 1));
            while (!queue.isEmpty()) {
                State cur = queue.poll();
                // 访问cur节点，同时知道它的路径权重和
                System.out.println("depth = " + cur.depth + ", val = " + cur.node.val);

                // 把cur的左右子节点加入队列
                if (cur.node.left != null) {
                    queue.offer(new State(cur.node.left, cur.depth + 1));
                }
                if (cur.node.right != null) {
                    queue.offer(new State(cur.node.right, cur.depth + 1));
                }
            }
        }
    }

    static class State {
        TreeNode node;
        int depth;

        public State(TreeNode node, int depth) {
            this.node = node;
            this.depth = depth;
        }
    }

    // 在实际的算法问题中，DFS算法常用来穷举所有路径，BFS算法常用来寻找最短路径，这个是什么原因呢？
    // 因为二叉树的递归遍历和层序遍历就是最简单的DFS算法和BFS算法

    // 111. 二叉树的最小深度
    // 给定一个二叉树，找出其最小深度。
    // 最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
    // 说明：叶子节点是指没有子节点的节点。
    // 输入：root = [3,9,20,null,null,15,7]
    // 输出：2
    // 示例 2：
    // 输入：root = [2,null,3,null,4,null,5,null,6]
    // 输出：5
    static class MinDepth {
        // DFS 递归遍历和 BFS 层序遍历都可以解决这道题，先看 DFS 递归遍历的解法：

        // 记录最小深度（根节点到最近的叶子节点的距离）
        int minDepth = Integer.MAX_VALUE;
        // 记录当前遍历到的节点深度
        int currentDepth = 0;

        public int minDepth(TreeNode root) {
            if (root == null) {
                return 0;
            }
            // 根节点开始DFS遍历
            traverse(root);
            return minDepth;
        }

        void traverse(TreeNode root) {
            if (root == null) {
                return;
            }
            // 前序位置进入节点时，增加当前深度
            currentDepth++;
            // 如果当前节点是叶子节点，更新最小深度
            if (root.left == null && root.right == null) {
                minDepth = Math.min(minDepth, currentDepth);
            }
            traverse(root.left);
            traverse(root.right);

            // 后序位置离开节点时减少当前深度
            currentDepth--;
        }
        // 每当遍历到一条树枝的叶子节点，就会更新最小深度，当遍历完整棵树后，就能算出整棵树的最小深度。
        // 你能不能在不遍历完整棵树的情况下，提前结束算法？不可以，因为你必须确切的知道每条树枝的深度（根节点到叶子节点的距离），才能找到最小的那个。

        // 下面来看 BFS 层序遍历的解法。按照 BFS 从上到下逐层遍历二叉树的特点，当遍历到第一个叶子节点时，就能得到最小深度：

        public int minDepth1(TreeNode root) {
            if (root == null) {
                return 0;
            }
            int depth = 1;
            Queue<TreeNode> queue = new LinkedList<>();
            queue.offer(root);
            while (!queue.isEmpty()) {
                int sz = queue.size();
                for (int i = 0; i < sz; i++) {
                    TreeNode cur = queue.poll();
                    // 判断是否到达叶子节点
                    if (cur.left == null && cur.right == null) {
                        return depth;
                    }
                    // 将下一层的节点加入队列
                    if (cur.left != null) {
                        queue.offer(cur.left);
                    }
                    if (cur.right != null) {
                        queue.offer(cur.right);
                    }
                }
                // 这里增加步数
                depth++;
            }
            return depth;
            // 综上，你应该能理解为啥 BFS 算法经常用来寻找最短路径了：
            // 由于 BFS 逐层遍历的逻辑，第一次遇到目标节点时，所经过的路径就是最短路径，算法可能并不需要遍历完所有节点就能提前结束。
            // DFS 遍历当然也可以用来寻找最短路径，但必须遍历完所有节点才能得到最短路径。

            // 为什么 DFS 常用来寻找所有路径
            // 在寻找所有路径的问题中，你会发现 DFS 算法用的比较多，BFS 算法似乎用的不多。
            // 理论上两种遍历算法都是可以的，只不过 BFS 算法寻找所有路径的代码比较复杂，DFS 算法代码比较简洁。
            // 你想啊，就以二叉树为例，如果要用 BFS 算法来寻找所有路径（根节点到每个叶子节点都是一条路径），队列里面就不能只放节点了，
            // 而需要使用第三种写法，新建一个 State 类，把当前节点以及到达当前节点的路径都存进去，这样才能正确维护每个节点的路径，最终计算出所有路径。
            // 而使用 DFS 算法就简单了，它本就是一条树枝一条树枝从左往右遍历的，每条树枝就是一条路径，所以 DFS 算法天然适合寻找所有路径。

            // 综上，DFS 算法在寻找所有路径的问题中更常用，而 BFS 算法在寻找最短路径的问题中更常用。
        }
    }

    // 多叉树
    static class Node {
        int val;
        List<Node> children;
    }


    static class MultiBranchTree {
        void traverse(TreeNode root) {
            if (root == null) {
                return;
            }
            // 前序遍历
            traverse(root.left);
            // 中序遍历
            traverse(root.right);
            // 后序遍历
        }
        // 唯一的区别是，多叉树没有了中序位置，因为可能有多个节点嘛，所谓的中序位置也就没有什么意义了。

        // 递归遍历（DFS）
        void traverse(Node root) {
            if (root == null) {
                return;
            }
            // 前序遍历
            for (Node child : root.children) {
                traverse(child);
            }
            // 后序位置
        }

        // 层序遍历（BFS）
        // 多叉树的层序遍历和二叉树的层序遍历一样，都是用队列来实现，无非就是把二叉树的左右子节点换成了多叉树的所有子节点。
        // 写法一：第一种层序遍历写法，无法记录节点深度：
        void levelOrderTraverse(Node root) {
            if (root == null) {
                return;
            }
            Queue<Node> queue = new LinkedList<>();
            queue.offer(root);
            while (!queue.isEmpty()) {
                Node cur = queue.poll();
                // 访问cur节点
                System.out.println(cur.val);
                // 把cur的所有子节点加入队列
                for (Node child : cur.children) {
                    queue.offer(child);
                }
            }
        }

        // 写法二：第二种层序遍历写法，能够记录节点深度
        void levelOrderTraverse1(Node root) {
            if (root == null) {
                return;
            }
            Queue<Node> queue = new LinkedList<>();
            queue.offer(root);
            // 记录当前遍历的层数（根节点视为第1层）
            int depth = 1;
            while (!queue.isEmpty()) {
                int sz = queue.size();
                for (int i = 0; i < sz; i++) {
                    Node cur = queue.poll();
                    // 访问cur节点，同时知道它所在的层数
                    System.out.println("depth = " + depth + ", val = " + cur.val);
                    for (Node child : cur.children) {
                        queue.offer(child);
                    }
                }
                depth++;
            }
        }

        // 写法三：第三种能够适配不同权重边的写法

        class State {
            Node node;
            int depth;

            public State(Node node, int depth) {
                this.node = node;
                this.depth = depth;
            }
        }

        void levelOrderTraverse2(Node root) {
            if (root == null) {
                return;
            }
            Queue<State> queue = new LinkedList<>();
            // 记录当前遍历的层数（根节点视为第1层）
            while (!queue.isEmpty()) {
                State state = queue.poll();
                Node cur = state.node;
                int depth = state.depth;
                // 访问cur节点，同时知道它所在的层数
                System.out.println("depth = " + depth + ", val = " + cur.val);
                for (Node child : cur.children) {
                    queue.offer(new State(child, depth + 1));
                }
            }
        }
    }
}






























